class TreeNode {
     int val;
     TreeNode left = null;
     TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
}

public class Solution {









//    TreeNode maxNode = new TreeNode(Integer.MIN_VALUE);
//    TreeNode minNode = new TreeNode(Integer.MAX_VALUE);
//
//    public int getDis (TreeNode root) {
//        // write code here
//        // 找到最大最小的叶子结点
//        findMaxMinNode(root);
//
//        // 找到lca (公共祖先结点)
//        TreeNode lcaNode = findLcaNode(root);
//
//        int a = findNodeLen(lcaNode, maxNode);
//        int b = findNodeLen(lcaNode, minNode);
//
//        return a + b;
//    }
//
//    private int findNodeLen(TreeNode lcaNode, TreeNode node) {
//        if (lcaNode == null) return -1;
//
//        if (lcaNode.val == node.val) return 0;
//
//        int j = findNodeLen(lcaNode.left, node);
//
//        if (j == -1) {
//            j = findNodeLen(lcaNode.right, node);
//        }
//        if (j != -1){
//            j++;
//        }
//        return j;
//    }
//
//    // 找公共祖先结点
//    private TreeNode findLcaNode(TreeNode node) {
//        if (node == null) return null;
//        if (node.val == maxNode.val || node.val == minNode.val) {
//            return node;
//        }
//        TreeNode leftNode = findLcaNode(node.left);
//        TreeNode rightNode = findLcaNode(node.right);
//
//        if (leftNode == null) {
//            return rightNode;
//        } else if (rightNode == null) {
//            return leftNode;
//        } else {
//            return node;
//        }
//    }
//
//    private void findMaxMinNode(TreeNode root) {
//        if (root == null) return;
//
//        if (root.val > maxNode.val && root.left == null && root.right == null) {
//            maxNode.val = root.val;
//        }
//        if (root.val < minNode.val && root.left == null && root.right == null) {
//            minNode.val = root.val;
//        }
//        findMaxMinNode(root.left);
//        findMaxMinNode(root.right);
//    }
//
//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(2);
//        root.right = new TreeNode(3);
//        System.out.println(solution.getDis(root));
//    }


    // if (node == null) return -1;
    //
    //        if (node.val == maxNode.val || node.val == minNode.val) {
    //            return 0;
    //        }
    //
    //        int distance = findLcaNode(node.left);
    //
    //        if (distance != -1) {  // 说明在左子树中没有，那么去右子树中找
    //            findLcaNode(node.right);
    //        } else {
    //            distance += 1;
    //        }
    //        return -1;


//    public int cutRope (int n) {
//        // write code here
//        int[] dp = new int[n + 1];
//        for (int i = 2; i <= n; i++) {
//            int curMax = 0;
//            for (int j = 1; j < i; j++) {
//                curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
//            }
//            dp[i] = curMax;
//        }
//        return dp[n];
//    }



//    public String longestPalindrome(String s) {
//        // write code here
//        int n = s.length();
//        String ret = "";
//        for (int i = 0; i < n - 1; i++) {
//            for (int j = i + 1; j < n; j++) {
//                String substring = s.substring(i, j + 1);
//                if (func(substring)) {
//                    if (ret.length() < substring.length()) {
//                        ret = substring;
//                    }
//                }
//            }
//        }
//        return ret;
//    }
//
//    public boolean func(String s) {
//        char[] arr = s.toCharArray();
//        int l = 0, r = arr.length - 1;
//        while (l < r) {
//            if (arr[l++] != arr[r--]) {
//                return false;
//            }
//        }
//        return true;
//    }
//
//    public int calculate(String express) {
//        // write code here
//        Deque<Character> stack = new ArrayDeque<>();
//        char[] arr = express.toCharArray();z
//        int i = 0;
//        int sign = 1;
//        while (i < arr.length) {
//            if (arr[i] == ' ') {
//                i++;
//            } else if (arr[i] == '*') {
//
//            } else if (arr[i] == '+') {
//                sign = stack.peek();
//                i++;
//            } else if (arr[i] == '-') {
//                sign = -stack.peek();
//                i++;
//            } else if (arr[i] == '(') {
//
//            } else if (arr[i] == ')') {
//
//            } else if (arr[i] >= '0' && arr[i] <= '9') {
//                int num = 0;
//                while (arr[i] >= '0' && arr[i] <= '9') {
//                    num = num * 10 + (arr[i++] - '0');
//                }
//                stack.push((char) (num + '0'));
//            }
//        }
//    }



//    public int execute(ListNode listNode1, ListNode listNode2, int startIndex, int endIndex) {
//        // write code here
//        ListNode newHead = new ListNode(0);
//        ListNode cur = new ListNode(0);
//        newHead.next = cur;
//        if (listNode1 == null) {
//            return getRet(startIndex, endIndex, listNode2);
//        }
//        if (listNode2 == null) {
//            return getRet(startIndex, endIndex, listNode1);
//        }
//
//        // 遍历两个链表 合并
//        while (listNode1 != null && listNode2 != null) {
//            // 判断1 2 的值谁大
//            if (listNode1.val >= listNode2.val) {
//                cur.next = listNode2;
//                cur = cur.next;
//                listNode2 = listNode2.next;
//            } else {
//                cur.next = listNode1;
//                cur = cur.next;
//                listNode1 = listNode1.next;
//            }
//        }
//        if (listNode1 == null) {
//            cur.next = listNode2;
//        }
//        if (listNode2 == null) {
//            cur.next = listNode1;
//        }
//
//        // 遍历链表返回值
//        ListNode t = newHead.next;
//        return getRet(startIndex, endIndex, t.next);
//    }
//
//    private static int getRet(int startIndex, int endIndex, ListNode t) {
//        int i = 0;
//        int ret = 0;
//        while (t != null) {
//            if (i >= startIndex - 1 && i <= endIndex - 1) {
//                ret += t.val;
//            }
//            t = t.next;
//            i++;
//        }
//        return ret;
//    }


//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        // 注意 hasNext 和 hasNextLine 的区别
//        int t = in.nextInt();
//        for (int i = 0; i < t; i++) {
//            int p = in.nextInt();
//            int q = in.nextInt();
//            int x = 0;
//            int ret = 0;
//            // p / q
//            for (int j = 0; j < 100000; j++) {
//                int last = p;
//                if (p < q) {
//                    p *= 10;
//                }
//                int tmp = p / q;
//                if (tmp == x && last == (p % q) * 10) {
//                    ret = x;
//                    break;
//                }
//                x = tmp;
//            }
//            System.out.println(ret);
//        }
//    }
}